from typing import *


class Solution:

    def minimumTotal(self, triangle: List[List[int]]) -> int:
        ans = [triangle[0][0]]
        for i in range(1, len(triangle)):
            row = [triangle[i][0] + ans[0]]
            for j in range(1, i):
                row.append(triangle[i][j] + min(ans[j], ans[j - 1]))
            row.append(triangle[i][-1] + ans[-1])
            ans = row
        return min(ans)


s = Solution()
print(s.minimumTotal([[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]))
